package com.hyb.algorithm.data.struct.str;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: ybhu
 * @create: 2021/09/29 02:17
 * <p>
 * 49. 字母异位词分组
 * <p>
 * https://leetcode-cn.com/problems/group-anagrams/
 * <p>
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GroupAnagrams {


    public List<List<String>> groupAnagrams(String[] strs) {


        Map<String, List<String>> map = new HashMap<>();
        //遍历 strs
        // 放入map 中  key 要排序  用 freq数组
        for (String str : strs) {

            int[] freq = new int[26];

            int len = str.length();
            for (int i = 0; i < len; i++) {
                freq[str.charAt(i) - 'a']++;
            }

            StringBuilder stringBuilder = new StringBuilder(26);

            for (int i = 0; i < freq.length; i++) {
                stringBuilder.append(freq[i]);
                stringBuilder.append("#");
            }

            String key = stringBuilder.toString();

            List list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);

            map.put(key, list);
        }

        return new ArrayList<>(map.values());
    }

}
